import java.io.*;
import java.lang.Math;

class DecisionTree
{
	static private Attribute attribute;
	public double go(String sData,int sizeData,String sTest,int sizeTest,boolean b)
	{
		attribute = new Attribute(sizeData);
		String str;
		int i,j,k,t;
		double d;
		int correct = 0;
		int wrong = 0;		
		try
		{
			/**处理data文件*/
			BufferedReader dataInput = new BufferedReader(new FileReader(sData));
			k = 0;
			while((str = dataInput.readLine()) != null)
			{
				t = 0;
				j = str.indexOf(",");
				attribute.setValue(k,t,str.substring(0,j));
				/**识别continuous属性最大值和最小值*/				
				if(attribute.getIfContinuous(t) && !attribute.getValue(k,t).equals("?"))
				{
					if(Double.parseDouble(attribute.getValue(k,t)) > attribute.getMaxContinuous(t))
						attribute.setMaxContinuous(t,Double.parseDouble(attribute.getValue(k,t)));
					if(Double.parseDouble(attribute.getValue(k,t)) < attribute.getMinContinuous(t))
						attribute.setMinContinuous(t,Double.parseDouble(attribute.getValue(k,t)));
				}				
				str = str.substring(j+1);
				while((j = str.indexOf(","))!= -1)
				{
					t++;
					attribute.setValue(k,t,str.substring(1,j));
					/**识别continuous属性最大值和最小值*/
					if(attribute.getIfContinuous(t) && !attribute.getValue(k,t).equals("?"))
					{
						if(Double.parseDouble(attribute.getValue(k,t)) > attribute.getMaxContinuous(t))
							attribute.setMaxContinuous(t,Double.parseDouble(attribute.getValue(k,t)));
						if(Double.parseDouble(attribute.getValue(k,t)) < attribute.getMinContinuous(t))
							attribute.setMinContinuous(t,Double.parseDouble(attribute.getValue(k,t)));
					}
					str = str.substring(j+1);
				}
				j = str.indexOf(".");
				str = str.substring(1,j);
				if(str.equals("50000+"))
					attribute.setResult(k,true);
				else
					attribute.setResult(k,false);
				k++;
			}
			
			/**决策树的学习过程*/
			Node root = Attribute.root;
			root.sum = 0;
			int set[] = new int[sizeData];
			boolean attributeSet[] = new boolean[41];
			for(i = 0;i < sizeData;i++)
				set[i] = i;
			for(i = 0;i < 41;i++)
				attributeSet[i] = true;
			root.ID3(sizeData,set,attributeSet,41,b);
			/**剪枝过程*
			int attributeName;	
			Node testNode = root;
			while(!testNode.isLeaf())
			{
				int correctValid = 0;
				int wrongValid = 0;
				double resultValid1;
				double resultValid2;
				attributeName = testNode.getName();				
				/**假如本层是连续属性*
				if(attribute.getIfContinuous(attributeName))
				{
					for(i = 0;i < 10;i++)
					{
						if(testNode.getNext(i).isLeaf == false)
						{
							for(j = 0;j < Attribute.validSize;j++)
							{
								k = Attribute.validSet[j];
								if(Attribute.getResult(k) == test(root,Attribute.value[k]))
									correctValid ++;
								else
									wrongValid++;
							}
							resultValid1 = ((double)correctValid)/(correctValid + wrongValid);							
							testNode.getNext(i).isLeaf = true;
							for(j = 0;j < Attribute.validSize;j++)
							{
								k = Attribute.validSet[j];
								if(Attribute.getResult(k) == test(root,Attribute.value[k]))
									correctValid ++;
								else
									wrongValid++;
							}
							resultValid2 = ((double)correctValid)/(correctValid + wrongValid);
							if(resultValid1 < resultValid2)
								testNode.getNext(i).isLeaf = false;
						}
					}
				}
			}
			*/
			/**决策树的检验过程*/
			BufferedReader testInput = new BufferedReader(new FileReader(sTest));
			String value[] = new String[41];
			boolean result;
			while((str = testInput.readLine()) != null)
			{	
				/**取每一行示例的属性*/
				k = 0;
				while((i = str.indexOf(","))!= -1)
				{
					if(k == 0)
						value[k] = str.substring(0,i);
					else
						value[k] = str.substring(1,i);
					str = str.substring(i+1);
					k++;
				}
				i = str.indexOf(".");
				str = str.substring(1,i);
				/**示例的目标答案*/
				if(str.equals("50000+"))
					result = true;
				else
					result = false;
				/**运用决策树猜测结果*/
				if(result == test(root,value))
					correct++;
				else
					wrong++;
			}
		}
		catch(IOException e)
		{
			System.out.println("程序出现IO异常！");
		}
		return (double)correct/(correct+wrong);		
	}
	public static boolean test(Node testNode,String value[])
	{
		int attributeName;	
		double d;
		int t,i;	
		while(!testNode.isLeaf())
			{
				attributeName = testNode.getName();
				/**假如本层是连续属性*/
				if(attribute.getIfContinuous(attributeName))
				{
					/**处理遗漏时的情况*/
					if(value[attributeName].equals("?"))
						testNode = testNode.getNext(10);
					else
					{
						/**判断元素所在的区间*/
						d = (Double.parseDouble(value[attributeName]) - attribute.getMinContinuous(attributeName))/(attribute.getMaxContinuous(attributeName) - attribute.getMinContinuous(attributeName))*10;
						t = (new Double(d)).intValue();
						if(t == 10) t = 9;
						testNode = testNode.getNext(t);
					}
				}
				/**如果本层不是连续属性*/
				else
				{
					/**处理遗漏时的情况*/
					if(value[attributeName].equals("?"))
						testNode = testNode.getNext(attribute.getNum(attributeName));
					else
					{
						for(i = 0;i < attribute.getNum(attributeName);i++)
						{
							if(value[attributeName].equals(attribute.getName(attributeName,i)))
							{									
								testNode = testNode.getNext(i);
								break;
							}
						}
					}
				}
			}
		return testNode.getResult();
	}
}
